//给你一个字符串 s，找到 s 中最长的 回文 子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
//
// Related Topics 双指针 字符串 动态规划 👍 7476 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2025-01-02 23:03:26
 * @description 5.最长回文子串
 */
public class LongestPalindromicSubstring{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LongestPalindromicSubstring fun=new LongestPalindromicSubstring();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/*动态规划
	 * 用 P(i,j)P(i,j) 表示字符串 ss 的第 ii 到 jj 个字母组成的串（下文表示成 s[i:j]s[i:j]）是否为回文串：
	 * 边界p(i,i)=true  p(i,i+1)=(si==si+1)
	 * p(i,j)=p(i+1,j-1)^(si=sj)
	 *
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n^2)
	 * */
	public String longestPalindrome1(String s) {
		int len=s.length();
		if(len<2) return s;
		int maxL=1;
		int start=0;
		//dp[][]表示s[i,j]是否是回文
		boolean[][] dp = new boolean[len][len];
		//初始化，所有长度为1即i=i的都是回文
		Arrays.setAll(dp, i->{
			boolean[] row = new boolean[len];
			row[i]=true;
			return row;
		});
		char[] chars = s.toCharArray();
		//开始，先枚举子串长度
		for (int L = 2; L <=len; L++) {
			//枚举左边界
			for (int i = 0; i < len; i++) {
				//由j-i+1=L.得出右边界
				int j = L + i - 1;
				//越界退出
				if(j>=len){
					break;
				}

				//赋值
				if(chars[i]!=chars[j]){
					dp[i][j]=false;
				}else{
					//不相等，且连续的两个一样的
					if(j-i<3){
						dp[i][j]=true;
					}else{
						//dp[i][j]为true等价于char[i]=char[j]且dp[i+1][j-1]为true
						dp[i][j]=dp[i+1][j-1];
					}
				}
				//遍历完，如果dp[i][L]==true，保存当前的位置和长度
				if(dp[i][j]&&j-i+1>maxL){
					maxL=j-i+1;
					start=i;
				}
			}
		}
		return s.substring(start,start+maxL);
	}

	/*
    中心拓展法
    P(i,j)←P(i+1,j−1)←P(i+2,j−2)←⋯←某一边界情况
    所有的状态在转移的时候的可能性都是唯一的
    边界情况即为子串长度为 11 或 22 的情况。
    我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。
    如果两边的字母相同，我们就可以继续扩展，
    例如从 P(i+1,j-1)P(i+1,j−1) 扩展到 P(i,j)P(i,j)；如果两边的字母不同，
    我们就可以停止扩展，因为在这之后的子串都不能是回文串了。
    时间复杂度：O(n^2)
    空间复杂度：O(1)O(1)。
    * */
	public String longestPalindrome2(String s) {
		int len=s.length();
		if(len<2) return s;
		int start=0,end=0;
		for (int i = 0; i < len; i++) {
			//边界可能为1，也可能为2（aba  abba)
			int ex1 = expand(s, i, i);
			int ex2 = expand(s, i, i + 1);
			int maxL = Math.max(ex1, ex2);
			//如果扩散有效，修改边界
			if(maxL>end-start){
				start=i-(maxL-1)/2;
				end=i+maxL/2;
			}
		}
		return s.substring(start,end+1);
	}
	private int expand(String s,int l,int r){
		while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
			--l;
			++r;
		}
		return r-l-1;
	}
	public String longestPalindrome3(String s) {
		StringBuffer stringBuffer = new StringBuffer(s);
		return null;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
